// 堆结构和堆排序，填函数练习风格
// 测试链接 : https://leetcode.cn/problems/sort-an-array/

#include <bits/stdc++.h>

using namespace std;

class Solution 
{
private:
    // i位置的数，向上调整大根堆
	// arr[i] = x，x是新来的！往上看，直到不比父亲大，或者来到0位置(顶)
    void heapInsert(vector<int>& nums, int i)
    {
        while(nums[i] > nums[(i - 1) / 2])
        {
            swap(nums[i], nums[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    // i位置的数，变小了，又想维持大根堆结构
	// 向下调整大根堆
	// 当前堆的大小为sz
    void heapify(vector<int>& nums, int i, int sz)
    {
        int l = 2 * i + 1;
        while(l < sz)
        {
            int best = l + 1 < sz && nums[l + 1] > nums[l] ? l + 1 : l;
            best = nums[best] > nums[i] ? best : i;
            if(best == i) break;
            swap(nums[best], nums[i]);
            i = best;
            l = 2 * i + 1;
        }
    }

	// 从顶到底建立大根堆，O(n * logn)
	// 依次弹出堆内最大值并排好序，O(n * logn)
	// 整体时间复杂度O(n * logn)
    void heapSort1(vector<int>& nums)
    {
        int n = nums.size();
        for(int i = 0; i < n; ++i)
        {
            heapInsert(nums, i);
        }

        int sz = n;
        while(sz > 1)
        {
            swap(nums[0], nums[--sz]);
            heapify(nums, 0, sz);
        }
    }

	// 从底到顶建立大根堆，O(n)
	// 依次弹出堆内最大值并排好序，O(n * logn)
	// 整体时间复杂度O(n * logn)
    void heapSort2(vector<int>& nums)
    {
        int n = nums.size();
        // 这里我将 i 改成 (n - 1 - 1) / 2
        // 从第一个非叶子节点开始向下调整
        // 因为叶子节点也已经不能往下调整了
        for(int i = (n - 2) / 2; i >= 0; --i)
        {
            heapify(nums, i, n);
        }

        int sz = n;
        while(sz > 1)
        {
            swap(nums[0], nums[--sz]);
            heapify(nums, 0, sz);
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) 
    {
        if(nums.size() > 1)
        {
            // heapSort1为从顶到底建堆然后排序
            // heapSort2为从底到顶建堆然后排序
            // 用哪个都可以
            // heapSort1(nums);
            heapSort2(nums);
        }
        return nums;
    }
};